package leetcode.top100;

import leetcode.a_总结分布.Code06_二叉树相关拓展;
import utils.TreeNode;

/**
 * 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。
 * <p>
 * 这条路径可能穿过根结点。
 * <p>
 * 示例 :
 * 给定二叉树
 * <p>
 *  1
 * / \
 * 2   3
 * /\
 *4 5
 * 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
 * <p>
 * 注意：两结点之间的路径长度是以它们之间边的数目表示。
 * <p>
 * <p>
 * 思路：本质是求树的高度。以当前位置为例，求出其左孩子l和右孩子r，
 * 那么从其左孩子到右孩子的路径就是l+r。
 * <p>
 * 如根节点，左孩子高2，右孩子高1，那么路径就是3.
 * <p>
 * 相同递归思想的题目{@link Code06_二叉树相关拓展#height()}
 *
 * @since 2019/12/23 0023 下午 5:03
 */
public class Code543_二叉树直径 {
    /**
     *
     * 分析：case1：路径是 左+当前+右。  这种情况不能递归！
     *   case2：路径是 当前+左右中的最大值，返回给父节点。
     */
    private int res = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) return res;
        process1(root);
        return res - 1;
    }

    private int process1(TreeNode root) {
        if (root == null) return 0;
        int left = process1(root.left);
        int right = process1(root.right);
        //case1:当前路径是：左孩子+当前节点+右孩子
        res = Math.max(res, left + right + 1);
        //case2:当前路径是：当前节点+左右孩子中较大值，返回给父节点
        int case2 = Math.max(left, right) + 1;
        //事实上这里不需要更新res，因为case2会返回给上层，上层还会更新res。
        res = Math.max(res, case2);
        //返回case2递归，case1无法递归
        return case2;
    }
    private int process2(TreeNode root) {
        if (root == null) return 0;
        int left = process2(root.left);
        int right = process2(root.right);
        //case1:当前路径是：左孩子+当前节点+右孩子
        res = Math.max(res, left + right + 1);
        //case2:当前路径是：当前节点+左右孩子中较大值，返回给父节点
        return Math.max(left, right) + 1;
    }
}
